Slide 22

Constructing a Tree from Postfix

We use a stack to build the tree from the expression: 3 4 + 5 *

T

If token is an Operand:

Create a single-node tree and push it onto the stack.

+

If token is an Operator:

1. Pop two trees (T2, then T1) from the stack.
2. Create a new root with the operator.
3. Attach T1 as the left child and T2 as the right child.
4. Push the new tree back onto the stack.

Step-by-Step Process

1. Read '3' (Operand)

Node('3')

2. Read '4' (Operand)

Node('4')
Node('3')

3. Read '+' (Operator)

Tree(root='+')

4. Read '5' (Operand)

Node('5')
Tree(root='+')

5. Read '*' (Operator)

Tree(root='*')

Final Result